package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/12 14:06
 */
public class M0801 {

    // https://leetcode-cn.com/problems/three-steps-problem-lcci/
    public static int waysToStep(int n) {
        if (n < 3) {
            return n;
        }
        return process(0, n);
    }

    private static int process(int cur, int n) {
        if (cur > n) {
            return 0;
        }
        if (cur == n) {
            return 1;
        }
        int ans = 0;
        for (int i = 1; i <= 3; i++) {
            ans += process(cur + i, n);
        }
        return ans;
    }

    public static int dp(int n) {
        if (n < 3) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[n] = 1;
        dp[n - 1] = 1;
        dp[n - 2] = 2;
        // 从右往左填
        for (int i = n - 3; i >= 0; i--) {
            long ans = 0;

            for (int step = 1; step <= 3; step++) {
                ans += dp[i + step];
            }

            dp[i] = (int) (ans % 1000000007);
        }
        return dp[0];
    }

    public static int dp2(int n) {
        if (n < 3) return n;
        long a = 1, b = 1, c = 2;
        long ans = 0;
        for (int i = n - 3; i >= 0; i--) {
            ans = (a + b + c) % 1000000007;
            a = b; b = c; c = ans;
        }
        return (int) ans;
    }


    // for test
    public static void main(String[] args) {
//        int n = 61;
        int n = 40;
//        System.out.println(waysToStep(n));
        System.out.println(dp(n));
        System.out.println(dp2(n));
    }

}
